package sorting

import (
	"fmt"
	"math/rand"
	"time"
)

func main() {
	number := 50 * 1
	arr := init2(number, number*2)

	now := time.Now().UnixNano() / 1e6

	//fmt.Printf("冒泡排序之后:%v \n", )
	bubbleSort(arr)
	now2 := time.Now().UnixNano() / 1e6

	fmt.Printf("冒泡排序时间: %d \n", now2-now)

	now = time.Now().UnixNano() / 1e6

	insertionSort(arr)
	//fmt.Printf("插入排序之后:%v \n", )

	now2 = time.Now().UnixNano() / 1e6

	fmt.Printf("插入排序时间: %d \n", now2-now)

	now = time.Now().UnixNano() / 1e6

	fmt.Printf("归并排序之后:%v \n", mergeSort(arr)[0])
	now2 = time.Now().UnixNano() / 1e6
	fmt.Printf("归并排序时间: %d \n", now2-now)

	now = time.Now().UnixNano() / 1e6
	mergeSort(arr)
	//fmt.Printf("快速排序之后:%v \n", )
	now2 = time.Now().UnixNano() / 1e6
	fmt.Printf("快速排序时间: %d \n", now2-now)
}

func Sort(src []int) (res [] int) {

	res = make([]int, len(src))

	copy(res, src)

	fmt.Printf("冒泡排序之前:%d \n", res[0])

	quickSort(res, 0, len(res)-1)

	fmt.Println(res)

	return nil
}

func quickSort(arr [] int, start, end int) {

	if start < end {
		i, j := start, end
		key := arr[(start+end)/2]
		for i <= j {
			for arr[i] < key {
				i++
			}
			for arr[j] > key {
				j--
			}
			if i <= j {
				arr[i], arr[j] = arr[j], arr[i]
				i++
				j--
			}
		}

		if start < j {
			quickSort(arr, start, j)
		}
		if end > i {
			quickSort(arr, i, end)
		}
	}
}

func bubbleSort(aa []int) [] int {
	var res []int = make([]int, len(aa))

	copy(res, aa)

	fmt.Printf("冒泡排序之前:%d \n", res[0])

	preIndex, current := 0, 0

	for i := 1; i < len(res); i++ {

		preIndex, current = i-1, res[i]

		for preIndex >= 0 && res[preIndex ] > current {

			res[preIndex+1] = res[preIndex ];
			preIndex--;
		}

		res[preIndex+1] = current

	}

	return res;
}

func insertionSort(aa []int) [] int {

	var res []int = make([]int, len(aa))

	copy(res, aa)

	fmt.Printf("插入排序之前:%d \n", res[0])

	for i := 1; i < len(res); i++ {

		j, value := i-1, res[i]

		for ; j >= 0; j-- {
			if (res[j ] > value) {
				res[j+1] = res[j ]
			} else {
				break
			}
		}
		res[j+1] = value
	}

	return res;
}

func mergeSort(aa []int) [] int {

	var res []int = make([]int, len(aa))

	var temp []int = make([]int, len(aa))

	copy(res, aa)

	fmt.Printf("归并排序之前:%d \n", res[0])

	mergeSort_c(res, temp, 0, len(res)-1)

	return res;
}

func mergeSort_c(res, temp []int, left, right int) [] int {

	if left < right {

		mid := (left + right) / 2

		mergeSort_c(res, temp, left, mid)

		mergeSort_c(res, temp, mid+1, right)

		merge(res, temp, left, mid, right)

	}

	return res;
}

func merge(arr, temp []int, start, mid, end int) [] int {
	tmpArr := make([]int, end-start+1)

	i := start
	j := mid + 1
	k := 0
	for ; i <= mid && j <= end; k++ {
		if arr[i] < arr[j] {
			tmpArr[k] = arr[i]
			i++
		} else {
			tmpArr[k] = arr[j]
			j++
		}
	}

	for ; i <= mid; i++ {
		tmpArr[k] = arr[i]
		k++
	}
	for ; j <= end; j++ {
		tmpArr[k] = arr[j]
		k++
	}
	copy(arr[start:end+1], tmpArr)

	return arr;
}

//返回指定长度和最大数字的int数组
func init2(length, maxNum int) ( [] int) {

	arra := make([] int, length)

	rand.Seed(time.Now().UnixNano())

	for i := 0; i < length; i++ {

		(arra)[i] = rand.Intn(maxNum)

	}

	return arra;
}
